• 算法乐园 主页 笔记 刷题




      Algorithm-learning-notes

      算法笔记+个人代码(菜,仅供参考)

      (笔记未完成,正在更新)

      版本:2023-08-17

      基础算法总结

      题目参考:https://www.programmercarl.com/

      Algorithm-learning-notes基础算法总结数组1:二分查找数组3:有序数组的平方数组4:长度最小的子数组|滑动窗口排序专题:1插入排序数组的插入排序排序插入排序优化:折半插入排序链表的插入排序2希尔排序3冒泡排序数组的冒泡排序链表的冒泡排序4快速排序5选择排序数组的选择排序:链表的选择排序6堆排序无脑递归版本:(空间复杂度偏高)奇妙循环版本:复杂度分析:(对于循环版本的代码)应用:合并K个升序链表7归并排序复杂度分析对数组归并排序对链表归并排序8基数排序复杂度分析对链表基数排序链表1:移除链表元素链表2:设计链表链表3:反转链表链表4:两两交换链表中的节点链表5:删除链表的倒数第N个节点链表6:相交链表链表7:环形链表II*哈希表1: 有效的字母异位词哈希表2:两个数组的交集哈希表3:快乐数哈希表4:两数之和哈希表5:四数相加II哈希表6:赎金信哈希表6.9:两数之和 II - 输入有序数组哈希表7:三数之和字符串1:反转字符串字符串2:反转字符串II字符串3:替换空格字符串4:反转字符串中的单词字符串6:找出字符串中第一个匹配项的下标字符串7:重复的子字符串字符串8:有效数字方法1:暴力if-else方法2:有限状态自动机方法3:正则表达式字符串10:验证IP地址栈和队列4:有效的括号栈和队列5:删除字符串中的所有相邻重复项栈和队列6:逆波兰表达式求值栈和队列7:基本计算器栈和队列8:基本计算器II二叉树2.递归遍历二叉树3.非递归遍历先序遍历:后序遍历:中序遍历:*二叉树5:层序遍历二叉树6:翻转二叉树二叉树8:对称二叉树二叉树9:二叉树的最大深度二叉树10:二叉树的最小深度二叉树11:完全二叉树的节点个数方法1:二分查找+位运算方法2:寻找满二叉树二叉树12:平衡二叉树二叉树13:二叉树的所有路径二叉树15:左叶子之和二叉树16:找树左下角的值二叉树17:路径总和二叉树18:从中序与后序遍历序列构造二叉树, 从前序与中序遍历序列构造二叉树二叉树19:最大二叉树二叉树21:合并二叉树二叉树22:二叉搜索树中的搜索二叉树23:验证二叉搜索树二叉树24:二叉搜索树的最小绝对差二叉树25:二叉搜索树中的众数二叉树26:二叉树的最近公共祖先二叉树28:二叉搜索树的最近公共祖先二叉树29:二叉搜索树的插入操作二叉树30:删除二叉搜索树中的节点回溯2:组合回溯4:组合总和III回溯5:电话号码的字母组合回溯7:组合总和回溯8:组合总和II回溯9:分割回文串回溯10:复原IP地址回溯11:子集回溯13:子集II回溯14:递增子序列回溯15:全排列回溯16:全排列II回溯19:重新安排行程回溯20:N皇后回溯21:解数独贪心2:分发饼干贪心3:摆动序列贪心4:最大子数组和贪心6:买卖股票的最佳时机 II贪心7:跳跃游戏贪心8:跳跃游戏II贪心9:K次取反后最大化的数组和贪心11: 加油站贪心12:分发糖果贪心13:柠檬水找零贪心14:根据身高重建队列*贪心17:用最少数量的箭引爆气球*贪心18:无重叠区间贪心19:划分字母区间贪心20:合并区间贪心22:单调递增的数字贪心23:监控二叉树图论最小生成树:连接所有节点的最小费用prim普里姆算法Kruskal算法最短路径问题:Dijkstra算法Floyd算法代码随想录的刷题顺序:动态规划3:爬楼梯动态规划4:使用最小花费爬楼梯动态规划6:不同路径动态规划7:不同路径II动态规划8:整数拆分动态规划9:不同的二叉搜索树0-1背包系列 13~17动态规划13:分割等和子集动态规划14:最后一块石头的重量II动态规划16:目标和动态规划17:一和零完全背包系列 19~26动态规划19:零钱兑换II动态规划21:组合总和IV动态规划23:零钱兑换动态规划24:完全平方数动态规划26:单词拆分打家劫舍问题29-31动态规划29:打家劫舍动态规划30:打家劫舍II动态规划31:打家劫舍III股票问题32-38动态规划32.买卖股票的最佳时机动态规划34.买卖股票的最佳时机II动态规划35.买卖股票的最佳时机III动态规划36:买卖股票的最佳时机IV动态规划37:买卖股票的最佳时机含冷冻期动态规划38:买卖股票的最佳时机含手续费子序列问题动态规划41:最长递增子序列动态规划42:最长连续递增序列动态规划43:最长公共子序列动态规划44:最长公共子序列动态规划45:不相交的线动态规划46:最大子序和动态规划47:判断子序列动态规划48:不同的子序列动态规划49:两个字符串的删除操作动态规划50:编辑距离动态规划52:回文子串动态规划53:最长回文子序列动态规划54:切披萨的方案数灵神的刷题顺序:动态规划:从记忆化搜索到递推198打家劫舍70. 爬楼梯746. 使用最小花费爬楼梯2466.统计构造好字符串的方案数213.打家劫舍 II拆分类动态规划343.整数拆分96.不同的二叉搜索树0-1背包和完全背包494. 目标和(0-1背包)解法1. 回溯(暴力)解法:可以1952ms踩线通过解法2:灵神的0-1背包记忆递归模板记忆递归模板解题解法3: 数组递推的动态规划解法322. 零钱兑换416. 分割等和子集1049.最后一块石头的重量II279. 完全平方数518. 零钱兑换 II377.组合总和IV474. 一和零879.盈利计划最长公共子序列1143.最长公共子序列72. 编辑距离583. 两个字符串的删除操作712. 两个字符串的最小ASCII删除和1458. 两个子序列的最大点积97. 交错字符串单调栈1:每日温度单调栈2:下一个更大元素I

      数组1:二分查找

      手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找(参考视频)

      leetcode704

      左闭右闭模板:

      注意四个细节:

      C++

      python:

      左闭右开模板:

      注意四个细节:

      C++:

      python:

      数组3:有序数组的平方

      双指针法经典题目 | LeetCode:977.有序数组的平方(参考视频)

      leetcode977

      推荐双指针法,由绝对值最小的数开始往两边遍历

      当然也可以由两边向中间遍历数组

      python:

      数组4:长度最小的子数组|滑动窗口

      leetcode209

      拿下滑动窗口! | LeetCode 209 长度最小的子数(参考视频)

      python:

      排序专题:

      数组排序:leetcode912

      单链表排序:leetcode148(测试用例很容易超时,matrix的面试题,当年我就没做出来😖)

      对链表进行插入排序:leetcode147(不容易超时)

      image-20230726124830123

      1插入排序

      支持数组和链表

      数组的插入排序排序

      空间复杂度O(1),因为只使用了常数个临时变量

      最好时间复杂度:O(n),对应于数组已经有序的情况

      最坏时间复杂度:O(n2),对应数组完全逆序的情况

      平均时间复杂度:O(n2)

      具有稳定性

      (在leetcode912提交会超时.leetcode147通过)

      插入排序优化:折半插入排序

      当遍历到第i个1元素时,[0,i-1]的所有元素时有序的,可以利用二分查找的方法找到插入位置

      然鹅, 时间复杂度没有质的飞跃

      空间复杂度O(1)

      最好时间复杂度:O(n),对应于数组已经有序的情况

      最坏时间复杂度:O(n2),对应数组完全逆序的情况

      平均时间复杂度:O(n2)

      具有稳定性

      (在leetcode912提交会超时)

      链表的插入排序

      空间复杂度:O(1),只额外开辟了常数级别的空间

      最好时间复杂度:O(n),对应于数组已经有序的情况

      最坏时间复杂度:O(n2),对应数组完全逆序的情况

      平均时间复杂度:O(n2)

      具有稳定性

      (在leetcode148提交会超时,leetcode147提交通过,16ms,9.3MB)

      2希尔排序

      仅支持数组,不适用链表

      先追求表中元素部分有序,再逐渐逼近全局有序

      每一轮都按照一个给定的间隔进行插入排序,这个间隔应当逐渐减少,最后必须为1

      以下的代码中, 步长(间隔)从n2开始递减,每次变为原来的12,直到变为1

      空间复杂度:O(1)

      时间复杂度:和增量序列d1,d2,d3,的选择有关,目前无法用数学手段证明确切的时间复杂度

      最坏时间复杂度O(n2),也就是取d=1的时候,这时候希尔排序退化为插入排序

      n在某个范围内时,可达O(n1.3)

      不具有稳定性,例如:

      原始序列: 65 49 49

      第一趟:d=2 49 49 65

      第一趟:d=1 49 49 65

      (在leetcode912提交通过,224ms,65MB)

      3冒泡排序

      数组的冒泡排序

      可用于数组和链表

      空间复杂度:O(1)

      时间复杂度

      最好情况(有序):O(n)

      最坏情况(逆序):O(n2)

      平均时间复杂度:O(n2)

      具有稳定性

      (在leetcode912提交会超时)

      链表的冒泡排序

      (在leetcode148提交会超时,leetcode147通过112ms,9.3MB)

      4快速排序

      最好空间复杂度:O(log2n)

      最坏空间复杂度:O(n)

      最好时间复杂度:O(nlog2n)

      最坏时间复杂度:O(n2)

      平均时间复杂度O(nlog2n)

      如果每次选中的枢轴将待排序序列划分为均匀的两个部分,则递归深度最小,算法效率最高

      若数组原本就有序或逆序,则快速排序性能最差

      算法不稳定

      (在leetcode912提交会超时)

      5选择排序

      数组的选择排序:

      空间复杂度O(1)

      时间复杂度O(n2)

      不稳定,例如:主要原因是使用了swap函数,如果牺牲一些时间,整体后移所有元素以避免使用swap,算法可以变为稳定的

      原始序列 3 3 1

      排序后 1 3 3

      (在leetcode912提交会超时)

      链表的选择排序

      空间复杂度O(1)

      时间复杂度O(n2)

      具有稳定性

      (在leetcode148提交会超时,leetcode147通过,80ms,9.4MB)

      6堆排序

      只适用于数组

      堆排序利用大根堆,本质是按照节点序号(从1开始)存储在数组中的完全二叉树

      几个基本操作

      若完全二叉树中有n个节点,则

      若n个关键字序列L[1...n]满足下面某一条性质,则称为堆(Heap)

      如果下标从0开始,则:

      无脑递归版本:(空间复杂度偏高)

      leetcode912通过,308ms,65MB

      奇妙循环版本:

      leetcode912通过,204ms,65MB

      复杂度分析:(对于循环版本的代码)

      复杂度分析部分考虑下标从1开始

      二叉树高h=log2n+1

      i层最多有2i1个节点,只有第1~(h-1)层的节点才可能需要下坠处理,每次下坠最多对比2次,第i层节点下坠最多对比h-i次

      把整棵树调整为大根堆, 关键字对比次数:

      i=h112i12(hi)=i=h112i(hi)=j=1h12hjj=2hj=1h1j2j=2log2n+1(2h+12h1)2n2=4n

      所以建堆的过程中时间复杂度O(n)

      排序的过程中总共需要处理n-1个节点,每个节点最多需要下坠h-1层,时间复杂度O(nlog2n)

      总的时间复杂度O(nlog2n)

      空间复杂度O(1)

      堆排序不稳定,例如

      原始序列 1 2 2

      排序后 1 2 2

      应用:合并K个升序链表

      leetcode23

      利用小根堆的性质解决

      C++:

      7归并排序

      复杂度分析

      2路归并的归并树,形态上就是一棵倒立的二叉树

      二叉树的第h层最多有2h1个节点,若树高为h,满足n2h1

      h1=log2n

      n个元素进行二路归并排序,归并趟数=log2n

      每趟归并的时间复杂度O(n),算法的时间复杂度O(nlog2n)

      递归工作栈的空间复杂度为O(log2n),辅助数组的空间复杂度O(n)

      总的空间复杂度O(n)

      归并排序具有稳定性

      对数组归并排序

      leetcode912通过,312ms,67.1MB

      对链表归并排序

      leetcode148通过,368ms,95.18MB

      8基数排序

      复杂度分析

      通常针对链表实现,假设长度为n的线性表中每个节点aj的关键字由d元组(kjd1,kjd2,kjd3,,kj1,kj0)组成

      其中,0kjir1(0j<n,0id1),r称为基数

      空间复杂度O(n)

      一趟分配O(n),一趟收集O(r),总共d趟,时间复杂度O(d(n+r))

      对于leetcode148,105Node.val105,n[0,5×104]

      排序时加上105,保证所有数为正数,对于十进制数r=10,d不超过6

      所有该题时间复杂度O(n),空间复杂度O(n)

      基数排序是稳定的, 因为基你太稳

      对链表基数排序

      leetcode148通过,216ms,63.4MB

      链表1:移除链表元素

      leetcode203

      使用虚拟头节点:

      C++

      不使用虚拟头节点:

      python

      链表2:设计链表

      leetcode707

      单向链表(使用虚拟头节点):

      链表3:反转链表

      leetcode206

      方法1:栈

      时间复杂度O(n),空间复杂度O(n)

      方法2:双指针

      时间复杂度O(n),空间复杂度O(1)

      方法3:递归

      时间复杂度O(n),空间复杂度O(n)

      链表4:两两交换链表中的节点

      leetcode24

      链表5:删除链表的倒数第N个节点

      leetcode19

      快慢指针法:先将右指针右移n个节点,再将左右指针一起右移,直到右指针的下一个位置为nullptr,此时左指针指向待删除节点的上一个位置

      链表6:相交链表

      leetcode160

      链表7:环形链表II*

      leetcode142

      快慢指针法:

      快指针一次移动2个节点,慢指针一次移动1个节点,移动完成后才检查二者是否相遇,两者相对速度1个节点,所以不会存在快指针越过慢指针而没有检测到的情况

      对于慢指针 t=a+b

      可以证明慢指针在圈里的路程不足一圈,不是t=a+b+k(b+c), 因为慢指针进入圈内时,快指针已经在圈内,慢指针要转完一圈,快指针就会转两圈,所以在慢指针转完一圈之前,快指针就会和慢指针相遇

      对于快指针 2t=a+b+n(b+c)

      所以a=(n-1)(b+c)+c

      让两个指针分别从头节点和相遇点出发,二者一定会在环的入口处相遇

      时间复杂度O(n), 空间复杂度O(1)

      C++:

      python:

      哈希表1: 有效的字母异位词

      leetcode242

      简单题,大佬们可以直接跳过

      用数组代替哈希表

      哈希表2:两个数组的交集

      leetcode349

      简单题,大佬们可以直接跳过

      python:

      哈希表3:快乐数

      leetcode202

      哈希表4:两数之和

      leetcode1

      经典好题

      C++:

      python:

      哈希表5:四数相加II

      leetcode454

      四个for循环O(n4)会超时

      两组两个for循环,配合哈希表可以通过,时间复杂度O(n2)

      哈希表6:赎金信

      leetcode383

      简单题,大佬们可以直接跳过

      python:

      哈希表6.9:两数之和 II - 输入有序数组

      leetcode167

      这一题是给下一题打基础用的

      推荐看灵神的视频

      C++:

      python:

      哈希表7:三数之和

      leetcode15

      这题不好做 😫

      C++:

      python:

       

      字符串1:反转字符串

      leetcode344

      双指针交换就行

      C++:

      Javascript:

      字符串2:反转字符串II

      leetcode541

      字符串3:替换空格

      leetcode剑指offer05

      算法很简单,可以拿这个检验一下自己对库函数的熟悉程度

      Javascript:不用库函数

      直接调用库函数:

      python也有这个库函数:

      字符串4:反转字符串中的单词

      leetcode151

      JavaScript:

      大佬的调用内置函数解法:

      字符串6:找出字符串中第一个匹配项的下标

      leetcode28

      KMP算法的经典例题

      方法1:KMP算法

      next数组 样例1:

      aabaaf
      010120

      next数组 样例2:

      aabaaab
      0101223

      遍历next数组的指针指向下标为j处时,遇到不匹配,就回退到下标next[j-1]

      next数组的构造过程

      i指向后缀表的末尾,j指向前缀表的末尾,每轮循环需要判断前后缀表的末尾元素能否加入前后缀表中,也就是比较needle[i]needle[j]是否相等

      前缀表和后缀表等长,末尾元素加入前后缀表后,长度都是j+1

      初始化i=1j=0

      方法2:Rabin-Karp算法

      这个算法实际上就是哈希表,ChatGPT的解释:

      Rabin-Karp算法是一种字符串匹配算法,用于在一个文本串中查找一个模式串的出现位置。

      算法的基本思想是通过哈希函数将模式串和文本串的子串进行比较。首先计算模式串的哈希值,然后依次计算文本串中所有长度为模式串长度的子串的哈希值,并与模式串的哈希值进行比较。如果哈希值相同,再逐个比较子串和模式串的每个字符是否相同,直到找到完全匹配的子串或者遍历完所有子串。

      算法的优点是可以在平均情况下达到线性时间复杂度O(n+m),其中n是文本串的长度,m是模式串的长度。然而,在最坏情况下,算法的时间复杂度为O((n-m+1)m),即当哈希值的冲突比较多时,效率会下降。

      总结来说,Rabin-Karp算法通过哈希函数加速字符串匹配,适用于处理长文本串和短模式串的情况。它在实际应用中常被用于字符串搜索、文本编辑器等领域。

      字符串7:重复的子字符串

      leetcode459

      方法1:双指针

      方法2:转化为字符串匹配问题

      方法3:转化为字符串匹配问题,并利用KMP算法

      字符串8:有效数字

      leetcode65

      方法1:暴力if-else

      笨人的这段代码比较乱,建议去看方法2,更易理解

      0ms 5.8MB

      方法2:有限状态自动机

      参考文献

      1. 初始状态
      2. 符号位
      3. 整数部分
      4. 左侧有整数的小数点
      5. 左侧无整数的小数点(根据前面的第二条额外规则,需要对左侧有无整数的两种小数点做区分)
      6. 小数部分
      7. 字符 e
      8. 指数部分的符号位
      9. 指数部分的整数部分

      (图片出自力扣官方题解)

      image-20230812093747065

      最后只有cur==2||cur==3||cur==5||cur==8时返回true

      0ms 5.9MB

      方法3:正则表达式

      C++的正则表达式库

      正则表达式大全

      代码粘贴自评论区大佬

      正在表达式的构造耗时很长,所以建议采用第二段代码,避免重复构造

      1884ms,259.3MB

      12ms 9MB

      字符串10:验证IP地址

      正则表达式

      栈和队列4:有效的括号

      leetcode20

      相当基础的栈的应用

      栈和队列5:删除字符串中的所有相邻重复项

      leetcode1047

      栈和队列6:逆波兰表达式求值

      leetcode150

      以下为王道考研数据结构的笔记:栈在表达式求值中的应用

      序号表示各个运算符的执行顺序

      image-20230725205911577

      image-20230725210612767

      image-20230725213918526

      image-20230725222156240

      C++:

      栈和队列7:基本计算器

      leetcode224

      栈和队列8:基本计算器II

      leetcode227

      代码在上一题的基础上改了一下,可以支持对正负数的+-*/和括号运算

      二叉树2.递归遍历

      先序遍历模板

      C++:

      python:

      中序遍历模板:

      和上面代码基本一样,交换它们的顺序:

      后序遍历:

      二叉树3.非递归遍历

      用栈模拟递归的过程

      写出二叉树的非递归遍历很难么?这次让你不再害怕非递归!|二叉树的非递归遍历 | 二叉树的遍历迭代法 | 前序与中(参考视频)

      先序遍历:

      注意:因为栈是先进后出的,先将右子节点入栈,再让左子节点入栈

      C++:

      Python:

      后序遍历:

      前序遍历是按照 中左右 遍历的

      如果把前序遍历代码中

      颠倒顺序, 变成

      遍历顺序变成 中右左

      最后的arr数组进行反转,遍历序列就会变成 左右中 后序遍历序列

      C++:

      Python:

      中序遍历:*

      二叉树5:层序遍历

      leetcode102

      二叉树6:翻转二叉树

      leetcode226

      二叉树8:对称二叉树

      leetcode101

      二叉树9:二叉树的最大深度

      leetcode104

      二叉树10:二叉树的最小深度

      leetcode111

      二叉树11:完全二叉树的节点个数

      leetcode222

      方法1:二分查找+位运算

      (思路同力扣官方题解)

      时间复杂度:O(log2n)

      二叉树的深度h=log2(n+1)

      首先需要O(h)的时间确定二叉树的深度

      然后进行二分查找, 每次查找都要访问h个节点, 时间复杂度O(h), 在编号为2h12h1的节点之间进行二分查找(在2h1个节点之间进行二分查找),时间复杂度O(log(2h1))=O(h1).

      所以总的时间复杂度O(h2)=O(log2n)

      因为开辟了长为h的数组,空间复杂度为O(logn)

      方法2:寻找满二叉树

      参考视频

      这个方法利用递归, 更容易写😋

      利用性质:一棵深度为h的满二叉树,节点数量为2h1

      另外, 在C++中, 2n可以写作1 << n

      时间复杂度:O(log2n)

      考虑最坏的情况, 也就是二叉树最大层次只有一个节点的情况, 总共需要递归h层, 每层递归的时间复杂度为O(h), 所以总的时间复杂度为O(h2)=O(log2n)

      空间复杂度:O(log(n))

      在最坏的情况下, 需要递归h层, 故空间复杂度O(log(n))

      二叉树12:平衡二叉树

      leetcode110

      二叉树13:二叉树的所有路径

      leetcode257

      回溯法+dfs

      使用to_string()函数(包含于头文件#include<string>),快速将整数转化为字符串

      二叉树15:左叶子之和

      leetcode404

      这题还挺简单的😏

      二叉树16:找树左下角的值

      leetcode513

      方法1:失败案例(原因:利用对于完全二叉树的节点编号解题,编号过大造成溢出)

      idx的意义是节点在对应完全二叉树中的编号n

      深度h和n的关系为h=log2n+1

      左孩子的编号满足n=n<<1

      右孩子的编号满足n=(n<<1)+1

      方法2: 乖乖用层序遍历,不整花里胡哨的方法才能AC

      方法3:整点花里胡哨的,用回溯法

      利用性质: 在深度优先搜索中,同一层位于左侧的节点总是最先被搜索到

      二叉树17:路径总和

      leetcode112路径总和

      简单题,回溯解决,大佬可以跳过

      leetcode113路径总和II

      还是回溯,上面的代码稍微改动即可

      二叉树18:从中序与后序遍历序列构造二叉树, 从前序与中序遍历序列构造二叉树

      leetcode106从中序与后序遍历序列构造二叉树

      回溯法,有点复杂

      leetcode105 从前序与中序遍历序列构造二叉树

      和上题一样的思路

      二叉树19:最大二叉树

      leetcode654

      二叉树21:合并二叉树

      leetcode617

      一样的回溯思路

      二叉树22:二叉搜索树中的搜索

      leetcode700

      简单题,大佬请跳过

      二叉树23:验证二叉搜索树

      leetcode98

      别小看这题,坑巨多

      二叉树24:二叉搜索树的最小绝对差

      leetcode530

      相当于求二叉树中序遍历序列相邻元素的最小绝对差

      二叉树25:二叉搜索树中的众数

      leetcode501

      采用中序遍历就行

      二叉树26:二叉树的最近公共祖先

      leetcode236

      直接回溯

      二叉树28:二叉搜索树的最近公共祖先

      leetcode235

      和上一题差不多,这题是二叉搜索树,可以利用性质简化

      用指针t从根节点开始采用二分搜索,直到发现t==p||t==q,或者pq分别位于t两侧

      二叉树29:二叉搜索树的插入操作

      leetcode701

      简单题,大佬可跳过

      二叉树30:删除二叉搜索树中的节点

      leetcode450

      回溯2:组合

      leetcode77

      C++:

      python: 要注意几个global的使用

      回溯4:组合总和III

      leetcode216

      回溯5:电话号码的字母组合

      leetcode17

      方法1: 两层for循环模拟枚举

      方法2:递归回溯

      回溯7:组合总和

      leetcode39

      回溯8:组合总和II

      leetcode40

      回溯9:分割回文串

      leetcode131

      回溯10:复原IP地址

      leetcode93

      回溯11:子集

      leetcode78

      回溯13:子集II

      leetcode90

      回溯14:递增子序列

      leetcode491

      回溯15:全排列

      leetcode46

      回溯16:全排列II

      leetcode47

      方法1:在得到全排列数组后进行整体去重

      60ms,8.8MB

      方法2:在递归的同一层内避免插入相同元素到数组中,有效避免出现重复

      8ms,10.9MB

      回溯19:重新安排行程

      leetcode332

      回溯20:N皇后

      leetcode51

      回溯21:解数独

      leetcode37

      数独棋盘:

       012345678
      0         
      1         
      2         
      3         
      4         
      5         
      6         
      7         
      8         

      判断是否属于同一个3×3宫:比较x/3*10+y/3的大小

      贪心2:分发饼干

      leetcode455

      排序 + 双指针 + 贪心

      贪心3:摆动序列

      leetcode376

      python:

      贪心4:最大子数组和

      leetcode53

      这里考虑局部最优解

      从左到右遍历一次nums数组,遍历到第i个元素时,add的含义是选择nums[i]的条件下考虑前i个元素的最大子数组和

      然后用ret记录add的最大值

      C++:

      python:

      贪心6:买卖股票的最佳时机 II

      leetcode122

      动态规划章节也包含了这道题

      方法1:贪心

      相当于截取prices数组中的所有上升子数组,求出它们的首尾元素之差并求和

      C:

      python:

      方法2:奇妙的动态规划

      dfs[i][0]表示第i天结束不持有股票的最大利润pair.first

      dfs[i][1]表示第i天结束持有股票的最大利润pair.second

      C++:一维数组递推

      python:将一维数组压缩为更新两个变量

      贪心7:跳跃游戏

      简单贪心,只需维护bound作为当前能到达的最远位置

      C:

      python:

      贪心8:跳跃游戏II

      leetcode45

      C:

      贪心9:K次取反后最大化的数组和

      leetcode1005

      你可能都没意识到你用了贪心算法, 就不小心AC了

      python:

      贪心11: 加油站

      leetcode134

      难度蹭蹭上涨了

      据说用C++写O(n2)的暴力解法可以通过,感兴趣的可以试试😉

      贪心:

      C++:

      时间复杂度O(n),空间复杂度O(n)

      贪心12:分发糖果

      leetcode135

      方法1:自己的复杂方法

      ratings数组视为一个波, 各个下标处对应的数值为该处波的高度

      一次遍历,找到所有的波谷下标装入队列

      然后从队列逐个取出下标,从波谷向两侧遍历直到到达波峰, 对于严格上升的点糖果数为上一个位置的糖果数+1,平缓的点糖果数为1

      一个位置的糖果数可能被多次计算,取其中的最大值

      C++:

      方法2:大佬们的方法

      正反两次遍历

      python:

      贪心13:柠檬水找零

      leetcode860

      简单模拟就行,用生活经验,有10元就优先用10元找零,5元是万能的

      python:

      贪心14:根据身高重建队列*

      leetcode406

      有点难😭

      搬运自讨论区的精彩解释:https://leetcode.cn/problems/queue-reconstruction-by-height/discussion/comments/1809851

      上了第一节体育课,老师给大家排好了体操的队伍,可是大家脑子都很笨,记不清自己在哪,老师说,你就看前面有几个比自己高的就行!就像这样:

      该上第二节课的时候,大家记住了前面有几个比自己高的,却还是忘记了怎么排,老师见状让学生从高到低排好队,身高一样的,比自己高的越多,越往后面站,像这样:

      每次让最高的学生出来找自己的位置,第一个高个子[7,0]自然站到了第一个位置:

      而第二个高个子[7,1]知道有一个人大于等于自己的身高,站在了第一个人身后:

      第三个人[6,1]想了想,有一个人比自己高,那自己肯定站在第二位,于是就插队,现在也站到了第一个人身后:

      第四个人[5,0]想了想,没人比自己高,那自己肯定站在第一位,于是就插队,站到了队头:

      第五个人[5,2]想了想,有两个人比自己高,于是就插队,站到了第二个人后面,也就是第三个位置:

      第六个人[4,4]看了看眼前的队伍,比自己高的人都在里面,他安心的数着前面有四个人比自己高,心安理得的站到了第四个人身后:

      其实这道题的大概思路就是这样,只有先让身高高的先进入队伍,后面身高低的才能根据前面高的来找自己的位置

      C++:

      贪心17:用最少数量的箭引爆气球*

      leetcode452

      很经典的区间问题

      贪心18:无重叠区间

      leetcode435

      首先按照右边界的坐标从小到大排序,如果右边界坐标相等,就按照左边界从大到小排序

      然后从左到右遍历, 对于每个被遍历到的区间,都删除掉它后面所有与之相交的区间

      被删除的区间不会再参与遍历

      几种已经排好序的样例如下(带x的被删除掉)

      C++:

      贪心19:划分字母区间

      leetcode763

      和上面两题相似,也是区间重叠问题

      C++: 自己的糟糕代码

      大佬的优雅代码(搬运自https://leetcode.cn/problems/partition-labels/discussion/comments/31356):

      贪心20:合并区间

      leetcode56

      贪心22:单调递增的数字

      leetcode738

      方法1:从左到右遍历(作者的笨办法)

      将n各个位填入数组(字符串也行),从左到右遍历:

      当发现当前位数字比前一位数字小时,就开始修改字符串,修改完字符串就能返回结果

      修改规则为:前一位数字减1,当前位数字及之后所有位的数字一律为9

      例如6328,遍历到3时,将前1位减1得5,后面一律为9,得5999

      考虑一种情况,n=332,遍历到下标2时发现数字比前一位小,将下标为1处的3改为2,后面置为9后,得329不符合题意,这说明还需要另外加一个循环从下标为1处向前遍历,如果当前位置数字比前一位小了,就把当前位置数字置为9,前一位数字减一,处理后数字变为299

      C++: 0ms,59MB

      方法2:从右往左遍历(大佬的优雅方法)

      C++: 4ms,5.9MB

      大佬虽然优雅,但耗时有点长

      贪心23:监控二叉树

      leetcode968

      val: 1->安装监控 2->接受下方节点监控 3->接受上方节点监控

      图论

      最小生成树:连接所有节点的最小费用

      leetcode1584

      本题为边稠密图,更适合普里姆算法

      prim普里姆算法

      从某一个顶点开始构建生成树,每次将代价最小的新顶点纳入生成树,直到所有顶点都纳入为止

      SysuGLM的解释:

      Prim 算法是一种用于解决无向图最小生成树问题的贪心算法。它的基本思想是从一个顶点开始,不断地寻找与当前生成树距离最近的顶点,将其加入到生成树中,直到所有顶点都加入到生成树中为止。该算法是由捷克数学家 Vojtěch Jarník 于 1930 年发现的,并在 1957 年由美国计算机科学家 Robert C. Prim 重新发现,因此得名 Prim 算法。 以下是 Prim 算法的基本步骤:

      1. 初始化一个空的最小生成树 T。
      2. 任选图中一个顶点 v,将其加入到 T 中。
      3. 在图中寻找距离 T 最近的顶点 u,将边 (u, v) 加入到 T 中。
      4. 重复步骤 3,直到所有顶点都加入到 T 中。
      5. 得到的 T 即为原图的最小生成树。

      Prim 算法的时间复杂度取决于具体的实现方式。最简单的实现方式是用邻接矩阵表示图,其时间复杂度为 O(n^2),其中 n 为图的顶点数。使用优先队列和邻接表可以进一步优化算法的性能,将时间复杂度降低到 O(nlogn)。

      设总共V个节点,时间复杂度O(V2), 适用于边稠密图

      Kruskal算法

      SysuGLM的解释:

      Kruskal 算法是一种贪心算法,用于求解连通网的最小生成树。具体步骤如下:

      1. 将所有的边按照权重从小到大排序。
      2. 初始化一个空集合,用于存放已选择的边。
      3. 按照排序后的顺序依次遍历每条边,检查当前边的两个顶点是否属于同一个连通分量(可以使用并查集数据结构进行快速判断)。如果不属于同一个连通分量,那么将这条边加入到已选择的边的集合中,并合并这两个顶点所在的连通分量;如果已经属于同一个连通分量,那么跳过这条边。
      4. 当已选择的边的数量等于顶点数减一时,算法结束。此时已选择的边构成了连通网的最小生成树。 这种算法的时间复杂度为 O(ElogE),其中 E 是边的数量。

      该算法利用Quick Union版本的并查集, 有关并查集Quick Find和Quick Union版本的区别, 参考本文

      最后一个测试用例会超时😭

      最短路径问题:

      image-20230817173317209

      图出自王道考研数据结构

      参考视频【王道计算机考研 数据结构】

      例题:

      BFS算法比较基础,且只能处理不带权的图,这里就不介绍了

      Dijkstra算法

      求带权图的最短路径长度,局限是不能处理负权图

      对于一系列顶点V0,V1,...,Vn1组成的有向带权图,求V0到各个顶点的最短路径长度

      初始化三个数组:

      leetcode743通过,92ms,36.5MB

      Floyd算法

      Floyd算法更加通用,可以解决带负权值的图,但前提是最短路径存在

      3
      4
      -9
      A
      B
      C

      如上图所示,要求A到C的最短路径,如果选择的路径是沿着箭头一直前进,每循环一圈路径长度减2,A到C的路径可以无穷小,不存在最短路径

       

      leetcode743通过,160ms,37MB

      代码随想录的刷题顺序:

      动态规划3:爬楼梯

      点击跳转

      动态规划4:使用最小花费爬楼梯

      点击跳转

      动态规划6:不同路径

      leetcode62

      方法1:数学,利用组合数直接计算Cm+n2m1

      C:

      方法2:动态规划

      python:

      动态规划7:不同路径II

      leetcode63

      C:

      python:

      动态规划8:整数拆分

      点击跳转

      动态规划9:不同的二叉搜索树

      点击跳转

      0-1背包系列 13~17

      动态规划13:分割等和子集

      点击跳转

      动态规划14:最后一块石头的重量II

      点击跳转

      动态规划16:目标和

      点击跳转

      动态规划17:一和零

      点击跳转

      完全背包系列 19~26

      动态规划19:零钱兑换II

      点击跳转

      动态规划21:组合总和IV

      点击跳转

      动态规划23:零钱兑换

      点击跳转

      动态规划24:完全平方数

      点击跳转

      动态规划26:单词拆分

      leetcode139

      方法1:BFS(广度优先搜索)+记忆化搜索

      方法2:完全背包

      (出自代码随想录)

      单词就是物品,字符串s就是背包,单词能否组成字符串s,就是问物品能不能把背包装满。

      拆分时可以重复使用字典中的单词,说明就是一个完全背包!

      打家劫舍问题29-31

      动态规划29:打家劫舍

      点击跳转

      动态规划30:打家劫舍II

      点击跳转

      动态规划31:打家劫舍III

      leetcode337

      每个节点都有偷和不偷两种选择,用pair对组存储两种情况下的最大收益

      如果偷了当前节点,则左右节点都不能偷,只有一种情况

      如果不偷当前节点,有四种情况:偷左右节点、偷左不偷右、偷右不偷左、左右都不偷

      股票问题32-38

      动态规划32.买卖股票的最佳时机

      leetcode121

      方法1:贪心

      用双指针实现,左指针取最小值,右指针取最大值,差值就是最大利润

      C:

      方法2:动态规划

      维护两个变量,分别是have今天结束后 持有股票的最大利润,notHave今天结束后 不持有股票的最大利润

      python:

      动态规划34.买卖股票的最佳时机II

      详见贪心章节

      总结一下32题和34题的动态规划区别

      32题的特点是只能买一次

      34题的特点是无限次购买:

      除了标黄的部分,两题的递推公式都是一样的

      对比代码:

      32题:

      tp1=max(have,-prices[i])

      tp2=max(notHave,have+prices[i])

      34题:

      tp1=max(have,notHave-prices[i])

      tp2=max(notHave,have+prices[i])

      动态规划35.买卖股票的最佳时机III

      leetcode123

      本题是下一题的削减版,对应下一题的k=2情况

      动态规划:

      注意,如果你用的是C++,-inf不能简单地用INT_MIN代替,因为动态规划过程中可能会涉及到对INT_MAX减去一个正数的操作

        33500314
      0第一次持有-3-3-300000
      1第一次卖出-inf0222334
      2第二次持有-inf-inf-522222
      3第二次卖出-inf-inf-inf-52556

      python:

      C++: 实现上有些区别,比如将每次持有和卖出的两种情况压缩到对组内

      动态规划36:买卖股票的最佳时机IV

      leetcode188

      解析见上一题

      python:

      C++:

      动态规划37:买卖股票的最佳时机含冷冻期

      leetcode309

      方法1:划分出三种状态

        12302
      0持有股票-1-1-111
      1保持卖出股票00122
      2卖出股票-inf12-13

      python:

      方法2:两种状态(带下划线的初始化要特殊考虑)

        12302
      0不持有股票01223
      1持有股票-1-1-111

      python:记忆化递归

      C++:

      动态规划38:买卖股票的最佳时机含手续费

      leetcode714

      fee=2

        132849
      0不持有股票000558
      1持有股票-3-3-3-3-1-1

      python:递归

      C++:递推

      子序列问题

      动态规划41:最长递增子序列

      leetcode300

      n为nums数组长度

      方法1:动态规划

      dp[i]表示以i为结尾的最长子序列

      时间复杂度O(n2)

      方法2:贪心+二分查找

      g[i]为长度为i+1的子序列末尾元素的最小值

      贪心+二分查找,时间复杂度O(nlog(n))

      g数组性质:1、严格递增 2、只更新一个位置,更新的位置是第一个>=nums[i]的数的下标

      动态规划42:最长连续递增序列

      leetcode674

      简单题,大佬们可以跳过

      动态规划43:最长公共子序列

      leetcode718

      动态规划44:最长公共子序列

      点击跳转

      动态规划45:不相交的线

      leetcode1035

       1052152
      2001111
      5011122
      1011222
      2012223
      5012233
      dp[i][j]={dp[i1][j1]+1,nums1[i]=nums2[j]max{dp[i1][j],dp[i][j1]},nums1[i]nums2[j]

      python:

      动态规划46:最大子序和

      leetcode53

      代码随想录:

      dp[i]:包括下标i(以nums[i]为结尾)的最大连续子序列和为dp[i]

      1. 确定递推公式

      dp[i]只有两个方向可以推出来:

      • dp[i - 1] + nums[i],即:nums[i]加入当前连续子序列和
      • nums[i],即:从头开始计算当前连续子序列和

      一定是取最大的,所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

      C++

      python

      动态规划47:判断子序列

      leetcode392

      本题和45:不相交的线很像

      动态规划48:不同的子序列

      leetcode115

      dp(i,j)表示 字符串t的前i+1个字母(t[0:i+1]) 在 字符串s的前j+1个字母(s[0:j+1])的子序列中 出现的次数

      dp(i,j)s[j]babgbag
      t[i]11111111
      b01122333
      a00111144
      g00001115
      dp(i,j)={dp(i,j1)+dp(i1,j1),t[i]=s[j]dp(i,j1),t[i]s[j]

      解析:

      t[i]!=s[j]时,当前的两个字符不匹配,dp(i,j)=dp(i,j-1)t[0:i+1]和s[0:j+1]的匹配问题可以转化为t[0:i+1]s[0:j]的匹配问题。

      举个例子,s=“bab”和t=“ba”不同子序列数,等价于s=“ba”和t=“ba”的不同子序列数,因为前者两个串末尾不同,可以看作s1新增的末尾字母b对不同子序列数不构成影响

      t[i]==s[j]时,当前的两个字符匹配,dp(i,j)=dp(i,j-1)+dp(i-1,j-1)

      举个例子,s=“babgba”和t=“ba”的不同子序列数,等于s=“babgb”和g=“ba”的子序列数,加上s=“babgb”,t=“b”的子序列数。

      python:(记忆化递归)

      C++

      Javascript

      动态规划49:两个字符串的删除操作

      leetcode583

      这题本质上和动态规划43:最长公共子序列相同

      python:

      C

      动态规划50:编辑距离

      点击跳转

      动态规划52:回文子串

      leetcode647

      中心扩散解法:时间复杂度O(n2)

      动态规划解法也是O(n2),就懒得写了

      动态规划53:最长回文子序列

      leetcode516

      dp(i,j)表示在区间[i,j]内最长回文子序列的长度

      动态规划54:切披萨的方案数

      leetcode1444

      考察二维差分和三维动态规划

      此题定义了pi数组,pi[i][j]意义为pizza数组中左上角(i,j)到右下角(row-1,col-1)矩形区域内苹果总数

      dp(i,j,c)的意义为左上角(i,j)到右下角(row-1,col-1)矩形区域切c刀的方案总数


      灵神的刷题顺序:

      动态规划:从记忆化搜索到递推

      动态规划入门:从记忆化搜索到递推【基础算法精讲 17】(参考视频)

      198打家劫舍

      leetcode链接

      维护一个数组vec[i]表示从前i个房子中能获得的最大金额和

      vec[i]=max(vec[i-2]+nums[i],vec[i-1])

      如果选择偷当前第i间的,最优收益是偷前i-2间的收益加上本间的收益

      如果不偷当前第i间,最优收益是偷前i-1间的收益

      C++:

      Python:

      (灵神的递归做法)

      JavaScript:

      课后作业:

      70. 爬楼梯

      leetcode链接

      vec[i]表示到达第i级楼梯至少需要几步

      一次可以跨1或2阶,故vec[i]=vec[i-1]+vec[i-2]

      C:

      python:

      746. 使用最小花费爬楼梯

      leetcode链接

      用数组li[k]表示到达第k级的最小花费

      因为出发没有花费,li[0]=li[1]=0

      li[k]=min(li[k-1]+cost[k-1],li[k-2]+cost[k-2])

      python:

      2466.统计构造好字符串的方案数

      leetcode链接

      dfs[i]表示长度为i的字符串的好字符串数目

      dfs[0]=1,dfs[k]=0(k<0)

      dfs[i]=dfs[i-zero]+dfs[i-one]

      为了C++防溢出(python防爆内存),需要在计算过程中对m=109+7取余

      C++:

      python:

      213.打家劫舍 II

      leetcode链接

      本题和打家劫舍类似,可以套用上次的代码,因为首尾相接,从[0,n]间房获得的最大收益等价于

      max{从[0,n-1]间房获得的最大收益,从[1,n]间房获得的最大收益}

      C:

      python:

      Javascript:

      拆分类动态规划

      343.整数拆分

      leetcode链接

      参考视频

      解法1:动态规划

      定义dp[i]是整数i拆分后相乘能得到的最大整数(i>=2)

      dp[i]=max(j*(i-j),j*dp[i-j]) (1<=j<i)

      解法2: 数学

      粘贴自讨论区:

      If an optimal product contains a factorf >= 4, then you can replace it with factors2and f-2 without losing optimality, as 2*(f-2) = 2f-4 >= f. So you never need a factor greater than or equal to 4, meaning you only need factors 1, 2 and 3 (and 1 is of course wasteful and you'd only use it for n=2 and n=3, where it's needed).

      For the rest I agree, 3*3 is simply better than2*2*2, so you'd never use 2more than twice.

      C:

      96.不同的二叉搜索树

      leetcode链接

      参考视频

      C++: 数组动规

      python: 记忆化递归

      0-1背包和完全背包

      01背包:416. 分割等和子集 474. 一和零 494. 目标和 879. 盈利计划 1049. 最后一块石头的重量 II 1230. 抛掷硬币

      完全背包:1449. 数位成本和为目标值的最大数字 322. 零钱兑换 518. 零钱兑换 II 279. 完全平方数


      0-1背包 完全背包 基础算法精讲 18(视频链接)

      494. 目标和(0-1背包)

      leetcode链接

      解法1. 回溯(暴力)解法:可以1952ms踩线通过

      C++:

      解法2:灵神的0-1背包记忆递归模板

      记忆递归模板

      示例出自CSDN

      有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?

      为方便讲解和理解,下面讲述的例子均先用具体的数字代入,即:eg:number=4,capacity=8

      i(物品编号)1234
      w(体积)2345
      v(价值)3456

      上述例子的dp数组打印: (dfs(i,c)=max(dfs(i-1,c),dfs(i-1,c-w[i])+v[i]))

      dfs012345678
      -1000000000
      0003333333
      1003447777
      2003457899
      30034578910

      image-20230705180715673

      灵神0-1背包递归模板(python):

      上述模板的C++版本:

      本题需要对上述模板进行变形,变形方式如下图

      image-20230705202036945

      解题

      python:

      C++:

      解法3: 数组递推的动态规划解法

      本题相当于v[i]=1,w[i]=nums[i]的情况

      s=(i=0nnums[i])target

      本题等价于在nums中任意取几个数相加,满足和等于s2,求任意取几个数相加的方法总数

      例如nums=[1,2,3,1,2],target=-1

      只需在nums中任意取几个数相加,满足和等于5

      arr[i][j]012345
      -1100000
      0(1)110000
      1(2)111100
      2(3)111211
      3(1)122332
      4(2)123555

      arr[i][j]表示只考虑numsi个元素时,相加得到j的最多方法数

      arr[i][j]=arr[i-1][j]+arr[i-1][j-nums[i]]

      注意坑: s为奇数或s<0都应当返回0

      C++:

      python:

      322. 零钱兑换

      leetcode链接

      这是一个完全背包问题

      举例:

      arr[i][j]表示当前状态下所需最少硬币数

      arr[i][j]=min(arr[i-1][j],arr[i][j-coins[i-1]]+1)i1

      icoins01234567
      0 0
      1101234567
      2201122334
      3301112223
      4401111222
      5501111122

      C++:二维数组递推

      Python:(记忆化递归)

      优化:压缩为一维数组

      C++

      python:

      课后作业:

      416. 分割等和子集

      leetcode链接

      对于nums=[1,5,11,5]的测试用例

       01234567891011
       100000000000
      1110000000000
      5110001100000
      11110001100001
      5110002200012

      arr(i,c)=arr(i-1,c-num[i])+arr(i-1,c)

      完成第5行时最后一列非0,可以返回True

      记忆化递归

      python:

      代码中k从小到大进行枚举,相当于按照nums数组由短到长枚举,很多数组只考虑前面一小段就符合条件,这样可以减少递归层级,防止超出内存限制

      正常的二维数组动规:

      C++:

      Javascript:

      压缩为一维数组:

      Python:使用临时数组

      C++:carl模板的倒序递推

      注意:本题如果用C++,只能用递推公式dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);

      而不能用dp[j]+=dp[j-nums[i]],因为后者dp[i]的含义是当前枚举到的数中加和为i的所有组合总数,会溢出

      分割等和子集问题的变换:

      1049.最后一块石头的重量II

      leetcode链接

      对于stones=[a1,a2,,an]

      可以找到一种分割子集的方法,使两个子集[b1,b2,,bi][c1,c2,,cj]的和相差最小,相差记为s

      b1+b2++bi=c1+c2++cj+s

      (b1,b2,,bi,c1,c2,,cjstones)

      s就是最后石头的最小可能重量

      最后会把石头分成两堆,重量分别为addsu-add(add<=su-add)

      add的理论最大值为su//add(//是整除),只需让addsu//add开始枚举递减,直到找到一种石头组合是部分总重量为add

      对应的最后一块石头的重量为su-add-add=su-2*add

      python:

      C++:

      279. 完全平方数

      leetcode链接

      测试用例n=12:

      arr=[1,4,9]

      dfs0123456789101112
       0
      10123456789101112
      40123123423453
      90123123421233

      dfs(i,c)=min(dfs(i-1,c),dfs(i,c-arr[i])+1)

      递归会爆内存,所以只贴压缩为一维数组的递推代码

      C++:

      python:

      518. 零钱兑换 II

      leetcode链接

       012345
       100000
      1111111
      2112233
      5112234

      vec[i][j]=vec[i-1][j]+vec[i][j-coins[i-1]];

      二维数组法

      C++:

      (记忆化)递归法

      python:

      压缩为一维数组:

      C++:

      python:

      377.组合总和IV

      leetcode链接

      与上题几乎一样,区别使上一题求组合数,不考虑顺序,本题求排列数,考虑顺序

      只需交换两个for循环的顺序

      dp数组表:(nums=[1,2,3],target=4)

       01234
       10000
      111124
      211236
      311247

      二维数组:

      dp(i,c)={dp(i1,c),c<nums[i]dp(i1,c)+dp(nums.size()1,cnums[i]),cnums[i]

      一维数组:

      474. 一和零

      leetcode链接

      这是一个0-1背包问题,区别是背包容量是一个二维的情况,即要同时考虑0和1的容量

      w0[i]表示str[i]含有0的个数

      w1[i]表示str[i]含有1的个数

      dfs(i,c,d)表示只考虑前i个字符串,0的剩余容量为c,1的剩余容量为d的情况下,字串的最大长度

      dfs(i,c,d)=max{dfs(i-1,c,d),dfs(i-1,c-w0[i],d-w1[i])+1}

      方法1:灵神模板记忆化递归

      python:

      C++:

      方法2:三维数组动规

      C++:

      879.盈利计划

      leetcode链接

      python记忆化递归(会爆内存)

      python递推

      最长公共子序列

      最长公共子序列 编辑距离【基础算法精讲 19】 (参考视频)

      1143.最长公共子序列

      leetcode链接

      image-20230706112658119

      可以得到递推式:

      image-20230706112721998

      可以证明,简化后结果为

      dfs(i,j)={dfs(i1,j1)+1(s[i]=t[j])max{dfs(i1,j),dfs(i,j1)}(s[i]t[j])

      python:

      72. 编辑距离

      leetcode链接

      dp(i,j)={min{dp(i1,j),dp(i,j1),dp(i1,j1)}+1,word1[i]word2[j]dp(i1,j1),word1[i]=word2[j]
      dp(i,j)ros
      0123
      h1123
      o2212
      r3222
      s4332
      e5443

      课后作业:

      583. 两个字符串的删除操作

      leetcode链接

      点击跳转

      712. 两个字符串的最小ASCII删除和

      leetcode链接

      dp(i,j)={dp(i1,j1)+ascii(s1[i]),s1[i]=s2[j]max{dp(i1,j),dp(i,j1)},s1[i]s2[i]

      1458. 两个子序列的最大点积

      leetcode链接

        30-6
       0000
      20666
      10666
      -206618
      50151518
      dp(i,j)=max{dp(i1,j1)+nums1[i]nums2[j],dp(i1,j),dp(i,j1)}

      97. 交错字符串

      leetcode链接

      三维dp

      单调栈1:每日温度

      leetcode739

      C++:

      python:

      单调栈2:下一个更大元素I

      leetcode496

      原理和上一题一样,时间复杂度为O(nums1.length + nums2.length)